/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年04月25日
*   描    述：
*
================================================================*/

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
  int val;
  struct ListNode* next;
};

struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {
  if (l1 == NULL) {
    return l2;
  }
  if (l2 == NULL) {
    return l1;
  }

  struct ListNode* merged;
  if (l1->val <= l2->val) {
    merged = l1;
    merged->next = merge(l1->next, l2);
  } else {
    merged = l2;
    merged->next = merge(l1, l2->next);
  }

  return merged;
}

struct ListNode* sortList(struct ListNode* head) {
  // 快慢指针就可以得到链表的中间节点，然后对左右两部分再分别进行此操作，如此当左右各只有一个节点时开始进行合并排序。
  if (head == NULL || head->next == NULL) {
    return head;
  }

  struct ListNode* slow = head;
  struct ListNode* fast = head->next;

  while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
  }

  struct ListNode* mid = slow->next;
  slow->next = NULL;

  struct ListNode* left = sortList(head);
  struct ListNode* right = sortList(mid);

  return merge(left, right);
}

int main() {
  struct ListNode* currNode = NULL;
  struct ListNode* listA = (struct ListNode*)malloc(sizeof(struct ListNode));

  listA->val = 4;
  listA->next = (struct ListNode*)malloc(sizeof(struct ListNode));
  currNode = listA->next;

  currNode->val = 2;
  currNode->next = (struct ListNode*)malloc(sizeof(struct ListNode));
  currNode = currNode->next;

  currNode->val = 1;
  currNode->next = (struct ListNode*)malloc(sizeof(struct ListNode));
  currNode = currNode->next;

  currNode->val = 3;
  currNode->next = NULL;

  sortList(listA);
}
